/*
 * Copyright 2010-2012 Susanta Tewari. <freecode4susant@users.sourceforge.net>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package commons.util.graph;

import commons.util.ExceptionUtil;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * A list (path) of nodes starting with the leaf to the root.
 *
 * @author Susanta Tewari
 * @since Jan 31, 2012
 *
 * @param <N>
 * @param <E>
 */
public class LeafPath<N, E> {

    /** Field description */
    private final List<Node<N, E>> nodes;

    /**
     *
     * @param nodes
     */
    private LeafPath(List<Node<N, E>> nodes) {

        if (!nodes.get(0).isLeaf()) {
            ExceptionUtil.throwIllegalArgEx(getClass(), "First_Entry_Not_Leaf");
        }

        if (!nodes.get(nodes.size() - 1).isLeaf()) {
            ExceptionUtil.throwIllegalArgEx(getClass(), "Last_Entry_Not_Root");
        }

        this.nodes = nodes;
    }

    /**
     * Builds an instance from a leaf of a tree. It does not create new node instances.
     *
     * @param leafNode a leaf from a tree
     */
    public LeafPath(Node<N, E> leafNode) {

        if (!leafNode.isLeaf()) {
            ExceptionUtil.throwIllegalArgEx(getClass(), "Arg_Not_Leaf", leafNode);
        }

        nodes = new ArrayList<>(10);

        nodes.add(leafNode);

        Node<N, E> parent = leafNode.getParent();

        while (!parent.isRoot()) {

            nodes.add(parent);

            parent = parent.getParent();
        }

        nodes.add(parent);
    }

    /**
     * The number of nodes it contains.
     *
     * @return number of nodes on this path
     */
    public int nodeLength() {

        return nodes.size();
    }


    /**
     * The number of edges it contains.
     *
     * @return number of edges on this path
     */
    public int edgeLength() {

        return nodes.size() - 1;
    }


    /**
     * Iterates nodes from the leaf to the root of this path.
     *
     * @return
     */
    public Iterable<Node<N, E>> nodeIterator() {

        return new Iterable<Node<N, E>>() {

            @Override
            public Iterator<Node<N, E>> iterator() {

                return nodes.iterator();
            }
        };
    }


    /**
     * Iterates edges from the leaf to the root of this path.
     *
     * @return
     */
    public Iterable<Edge<N, E>> edgeIterator() {

        final List<Edge<N, E>> edges = new ArrayList<>(nodes.size() - 1);

        for (int i = nodes.size() - 1; i > 0; i--) {

            Edge<N, E> edge = nodes.get(i).getChildEdge(nodes.get(i - 1));

            edges.add(edge);
        }

        return new Iterable<Edge<N, E>>() {

            @Override
            public Iterator<Edge<N, E>> iterator() {

                return edges.iterator();
            }
        };
    }


    /**
     * Returns the leaf of this path.
     *
     * @return the path leaf
     */
    public Node<N, E> getLeaf() {

        return nodes.get(0);
    }


    /**
     * Returns the root of this path.
     *
     * @return the path root
     */
    public Node<N, E> getRoot() {

        return nodes.get(nodes.size() - 1);
    }


    /**
     * Creates a copy of this path. The new nodes do not copy all the children of the nodes
     * contained in this path. Only the nodes in the path are copied. The node and edge data are
     * copied by reference as they are assumed immutable.
     *
     * @return
     */
    public LeafPath<N, E> copy() {

        List<Node<N, E>> nodes_temp = new ArrayList<>(nodes.size());

        Node<N, E>       parent     = new Node<>(null, nodes.get(0).getData(), 1);

        for (int i = nodes.size() - 1; i > 0; i--) {

            nodes_temp.add(i, parent);

            Edge<N, E> edge = nodes.get(i).getChildEdge(nodes.get(i - 1));

            parent = parent.addChild(nodes.get(i - 1).getData(), edge.getData(), 1);

        }

        return new LeafPath<>(nodes_temp);
    }
}
